A content addressable memory (CAM) is a memory device that permits rapid parallel searching of stored data to find a particular data value. In contrast to most other memory formats (such as ROM and RAM memory), which are based on address-driven storage architectures, the typical CAM memory device offers both address-driven and content-driven data access.
Address-driven memory device architectures are well-known. According to an address-driven architecture, during a memory access, a user supplies an address and stores or retrieves data stored at that specific address. For example, in an address-driven data handling scheme, data values may be stored at a particular logical address by specifying the address on an address bus, and supplying data on a data bus to be stored at the specified address. This is the storage mechanism typically found in RAM memory. In the same fashion, data may be retrieved on the data bus in response to a memory address supplied on the address bus.
As noted, the typical CAM memory device can be accessed in both address-driven and content-driven fashion. Storage of data in a CAM may be performed in an address-driven mode, as described above. Additionally, some CAM memory devices allow storage of data in a “first available storage location.” For example a logical flag may be provided for each memory cell of the CAM device, indicating whether a cell contains stored data, or is available to receive new data. When a new data item is presented to the CAM device, each logical flag of the logical flag set is tested simultaneously and an unused storage location is identified. The new data item is then stored in the unused storage location, and the logical flag associated with that location is reconfigured to indicate that the location is in use.
As with data storage, data retrieval in a CAM memory may be performed on an address-driven basis. More importantly, however, CAM memory provides content-driven data retrieval. In a content-driven data search system, a data pattern is presented to the CAM memory device. If the CAM memory device contains a previously stored data item of the same data pattern, that presence is indicated and the location in the CAM where the searched data is stored is returned. The CAM memory device is structured to perform the search on a highly parallel basis, conducting the search on all the data in the CAM simultaneously. Consequently, a CAM can provide search results much more rapidly than an address-driven memory device, in which searches are typically performed serially, one address at a time.
The content-driven data retrieval facility described above makes CAM memory useful in the design of database management, pattern recognition, list management, and telecommunications hardware. CAM is particularly valuable in image and voice recognition systems, and in network switching equipment such as, for example, network routers in which CAM memory is used to convert between various address formats. Any technology that requires rapid content searching for an arbitrary data pattern may benefit from the application of CAM technology.
The content-driven data retrieval facility of a CAM memory is typically implemented by providing an array of storage cells connected in an extensive wired-or configuration. This architecture allows a multi-bit data word applied to an input of the CAM device to be compared, virtually simultaneously, with the data words stored in every location of the CAM.
FIG. 1 shows a simplified schematic representation of a CAM memory device, as known in the art. The CAM device 10 includes an array 100 of CAM memory cells 102 coupled in a first direction by complemented 114 and un-complemented 115 bit lines and in a second direction by match lines 110. The complemented bit lines 114 and un-complemented bit lines 115 are respectively coupled to un-complemented 34 and complemented 34 outputs of respective bit storage locations 30 of an input buffer. Thus, for example, when a “0” is stored in a bit storage location 30, the un-complemented bit lines 115 exhibits a “0” state and the complemented bit line 114 exhibits a “1”.
The array is arranged in words 103 of memory cells 102. Each word 103 is a given number of memory cells wide, the width corresponding to a width of the array 105. The array has a depth 107 equal to the number of words 103 of memory cells in the array. Each of the memory cells 102 includes a memory element 104 with an un-complemented output 111 and a complemented output 113.
Memory element 104 may be implemented in any of a wide variety of technologies as known in the art. For example, the memory element may be a static memory element as found in conventional static random access memory (SRAM) or a dynamic memory element as found in conventional dynamic random access memory (DRAM).
The un-complemented output 111 of memory element 104 outputs a signal representing a binary value stored within the memory element. The complemented output 113 outputs a signal representing the inverse of the value stored within the memory element 104.
The memory cell 102 also includes an un-complemented memory element transistor 108, a complemented memory element transistor 106, an un-complemented bit line transistor 123 and a complemented bit line transistor 121. For each memory element, the respective drains of the respective complemented 106 and un-complemented 108 memory element transistors are coupled to a respective match line 110 of the array 100. A source of the complemented memory element transistor 106 is coupled to a drain of the un-complemented bit line transistor 123. A source of the un-complemented memory element transistor 108 is coupled to the drain of the complemented bit line transistor 121. The sources of the complemented 121 and un-complemented 123 bit line transistors are mutually coupled to a source of ground potential 112. A gate of the complemented memory element transistor 106 is operatively coupled to the respective complemented output 113 of the memory element 104, so that the state of the memory element transistors reflect the logical state of the memory element. A gate of the un-complemented memory element transistor 108 is operatively coupled to the respective un-complemented output 111 of the memory element 104. The gates of the complemented bit line transistor 121 and the un-complemented bit line transistor 123 are coupled respectively to the complemented 114 and un-complemented 115 bit lines associated with the respective memory cell 102.
A plurality of precharge transistors 116 serve to switchingly couple each respective match line 110 to a source 118 of precharge potential. The respective gates of precharge transistors 116 are mutually coupled to a source of a precharge signal 132. Each match line 110 is coupled to a respective input of one of a plurality of buffer circuits 120. The buffer circuits 120 serve to amplify an electrical signal on the match line 110 and present an amplified signal at a respective output 122.
Each bit line 114, 115 is driven by a respective inverting driver 124 having an input 126 for receiving a data value and an output 128 coupled to the inverting bit line 114.
The intrinsic capacitance of each match line 110 is represented by capacitor 134 coupled between the bit line 110 and the source of ground potential 112. Together, the respective plurality of inputs D, of the register bit storage locations 30, form a data port 130 for receiving an input data value into the CAM device 10. The data port 130 has a width equal to the width 105 of each data word 103.
In operation, a search cycle of the CAM begins by precharging the match lines. A logical low signal from the precharge signal source causes the plurality of precharge transistors to conduct current from a source of precharge potential 118 onto respective match lines 110, charging the respective capacitance 134 of each match line. Thereafter, the precharge signal is brought high so as to disconnect the match lines 110 from the source of precharge potential 118. Data is then applied to the CAM to perform a content-based data access.
The bit values of a data word are applied at port 130. These bit values are stored in data buffer elements 30 and output in complemented and un-complemented form at outputs 34 and 32 respectively. The bit values are inverted again by the inverting drivers 124 so that the logical complement of the applied data word is present on the inverted bit lines 114. Concurrently non-inverted data values are available on the un-complemented bit lines 115.
Because the CAM memory cells 102 are coupled to the bit lines 110 in wired-or fashion any of the CAM memory cells 102 is capable of grounding, and thus discharging, the respective match line 110 to which is coupled. Any bit applied to an input of port 130 that does not match the bit value stored in the corresponding memory cell 104 causes the respective memory cell transistor and bit line transistor, acting together, to discharge the match line 110 coupled to that memory cell 104.
FIG. 2 graphically shows the operation of a simplified CAM device for an exemplary data word. Note that for clarity of illustration, the un-complemented bit lines 115 have been omitted from FIG. 2. Likewise, the respective un-complemented bit line transistors 123 and complemented memory element transistors 113 have been omitted from each memory cell 102 of FIG. 2. The complemented bit line transistors 121 and un-complemented memory element transistors 108 are shown.
In FIG. 2, one sees that the exemplary CAM device 10 comprises an array of twenty memory cells arranged in four five-bit words. The respective values of the five-bit words applied at the driver inputs 126 are 00001, 00010, 00011 and 00100. After precharging the device to charge the match lines 110, an input data word 00010 is applied at the respective inputs of the inverting line drivers 124. The inverters 124 complement the input data word yielding 11101 on the bit lines 114 as shown at 150.
Each respective digit of this data pattern is applied simultaneously to all the respective gates of the complemented bit line transistors 121 coupled to the respective bit line bearing the digit.
Examining particular memory cells, one sees that particular memory cell 152 includes a storage element 104 storing the value 0 and a bit line 114 bearing the value 1. Accordingly, although the bit line transistor is conductive, the storage element transistor is nonconductive and memory cell 152 does not couple the match line 110 to ground. Likewise, no one of particular memory cells 154, 156, and 158 provides a conductive path from the particular match line 164 to ground 112.
Memory cell 160, however, stores a value of 1 in its respective memory element. This value, in conjunction with the 1 value present on the particular bit line 162 coupled to memory cell 160 causes the memory cell 160 to ground the particular match line 164 and discharge the respective capacitance 134 of that match line. Thus, since the data word (00001) stored in the memory cells associated with the particular match line 164 does not equal the data value (00010) applied at the respective inputs of the inverting line drivers 124, the match line 164 transitions to a low state as quickly as the capacitance 134 of the bit line 110 can be discharged. In similar fashion, the data values associated with match lines 168 and 170 do not match the data word applied at the respective inputs of the inverting line drivers 124, and match lines 168 and 170 also rapidly discharge to ground potential.
The result for the particular match line 166 is different, however. The data values (00010) stored in the memory elements associated with the particular match line 166 are identical to those of the data word (00010) applied at the respective inputs of the inverting line drivers 124. When the complement of the applied data word (11101) is applied to the respective bit-line transistor gates of the memory cells coupled to particular match line 166, no path to ground is activated. Accordingly, the capacitance of particular match line 166 is not discharged, and match line 166 retains a voltage substantially equal to that supplied by the precharge voltage source 132. This precharge voltage on match line 166 indicates the match that exists between the data of match line 166 and the applied data word. Subsequently, the presence of this match may be output as a binary state, and/or the match indication may be used to output a further data value logically coupled to the matched data value, such as the storage address of the matching data word.
It is readily apparent that the un-complemented bit line transistors and complemented memory element transistors omitted from FIG. 2 would yield additional paths to ground for match lines associated with stored data words that do not match the data input to the CAM. For example, the complemented bit line transistor 121 and un-complemented memory element transistor 108 of the particular memory cell 158, as shown, do not ground the particular match line 164. Their complements, (i.e., the un-complemented bit line transistor and the complemented memory element transistor), however, would ground the particular match line 164 because the input bit has a value 1 and the stored bit has a value 0.
In the above-described search process, the searched data (i.e., the input bits) is simultaneously compared with every data word in the CAM in order to find a match between the stored data and the input data. Since the comparison operation is conducted simultaneously on the entire memory, and is typically repeated at a very high frequency, this operation consumes a significant amount of power. Accordingly, it is desirable to find a way to reduce power dissipation of CAM match detection circuits while maintaining the same levels of accuracy.
As known in the art, CAM arrays are typically much larger than the exemplary arrays illustrated in FIGS. 1 and 2. Without limiting the invention in any way, it is observed that CAM devices are known or contemplated with word widths of about 32 to about 320 bits wide. Such devices may readily include 64K words of memory cells. An exemplary CAM has a depth of approximately 64K 144 bit words. Thus each bit line is coupled to approximately 65 thousand bit line transistor gates. Consequently, the bit line will exhibit a capacitance resulting from at least the intrinsic capacitance of the bit line conductor and the capacitances of the 64K bit line transistor gates. This capacitance presents an appreciable load on the bit-line drivers 124 of the CAM. Moreover, because substantial current is required to charge the bit line capacitance, the resistance of the driver components, bit lines and gates subject to this current results in the dissipation in the CAM device of a correspondingly large amount of non-reactive power.
Power dissipation, P, in a circuit such as that depicted in FIG. 1, is related to the magnitude of signal swing, V, the load capacitance C, and the frequency of operation F (P=C*F*V2). In particular, power dissipation from a CAM device can be represented as (P=C*F*VDD*Vout) where Vout is the magnitude of the voltage swing during a bit line transition. As noted above, the CAM device is searched in parallel fashion. Consequently, during a search cycle every bit line of the device, and all of the transistor gates coupled to those bit lines, experience the entire voltage swing Vout of the bit line. Signal swing for conventional CAM device bit lines is from VDD to ground, and power is dissipated by the circuit accordingly. The power dissipated in the bit lines of a CAM can amount to approximately 40% of the power budget of a CAM device.
Device speed can be improved by dividing each bit line into segments, with repeating drivers coupling one segment to the next. While this reduces the load on the drivers 124, it costs additional chip real estate, and does nothing to reduce the overall capacitance and net power dissipation of the device.